//
// Created by liushuai on 2020/4/2.
//
#include "maxProfit.h"
int maxProfit(std::vector<int>& prices) {
  int min_price = std::numeric_limits<int>::max();
  int max_profit = 0;
  for (auto p : prices) {
    max_profit = std::max(max_profit, p - min_price);
    min_price = std::min(p, min_price);
  }
  return max_profit;
}
int maxProfitDp(std::vector<int>& prices) {
  if (prices.size() == 1) return 0;
  int length = prices.size();
  int* dp = new int[length];
  int min_price = prices[0];
  int max_profit = 0;
  for (int i = 1; i < length; i++) {
    dp[i] = std::max(dp[i - 1], prices[i] - min_price);
    min_price = std::min(prices[i], min_price);
    max_profit = std::max(max_profit, dp[i]);
  }
  delete[] dp;
  return max_profit;
}

int maxProfitMultDp(std::vector<int>& prices) {
  int length = prices.size();
  if (length == 0) return 0;
  int dp[length][2];

  dp[0][0] = 0;
  dp[0][1] = -prices[0];
  for (int i = 1; i < length; i += 1) {
    dp[i][0] = std::max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
    dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  }
  return dp[length - 1][0];
}

int maxProfitMultGreedy(std::vector<int>& prices) {
  int max_profit = 0;
  for (int i = 1; i < prices.size(); ++i) {
    max_profit += std::max(0, prices[i] - prices[i - 1]);
  }
  return max_profit;
}
